package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
	"time"
)

const (
	UP    = iota
	DOWN  = iota
	LEFT  = iota
	RIGHT = iota
)
const (
	QUERY = iota
	SAVE  = iota
)

var DirArr []byte = []byte{UP, DOWN, LEFT, RIGHT}

type State struct {
	grids     [9]byte
	xPos      byte
	hash      uint64 // grids的hash
	stateHash uint64 // grids + xPos的hash
	step      []byte // 到达当前状态所走的step
}

type AnsOp struct {
	ops      byte
	hash     uint64
	stepChan chan []byte
	steps    []byte
}

type Result struct {
	id   string
	step []byte
}

func initState(grids [9]byte, xPos byte, step []byte) State {
	hash := hashGrid(grids)
	stateHash := hashGridAndStart(grids, xPos)
	return State{grids, xPos, hash, stateHash, step}
}

func hashGridAndStart(_grids [9]byte, start byte) uint64 {
	num := uint64(start)
	var l uint64
	var i byte
	for i = 0; i < 9; i++ {
		l = uint64(_grids[i])
		num = num | (l << (4 + 4*i))
	}
	return num
}

func hashGrid(_grids [9]byte) uint64 {
	var num uint64 = 0
	var l uint64
	var i byte
	for i = 0; i < 9; i++ {
		l = uint64(_grids[i])
		num = num | (l << (4 * i))
	}
	return num
}

func dehashGrid(hash uint64) [9]byte {
	var grids [9]byte
	var i byte
	for i = 0; i < 9; i++ {
		grids[i] = byte(hash & 15)
		hash /= 16
	}
	return grids
}

func notDone(_grids [9]byte) bool {
	var i byte
	for i = 0; i < 9; i++ {
		if _grids[i] != i {
			return true
		}
	}
	return false
}

func exchange(_grids [9]byte, pos1 byte, pos2 byte) [9]byte {
	// [9]byte定义的是整型数组(长度9),数组是按值传递的
	tmp := _grids[pos1]
	_grids[pos1] = _grids[pos2]
	_grids[pos2] = tmp
	return _grids
}

func goNextState(_grids [9]byte, dir byte, pos byte, step []byte) interface{} {
	var newStep byte
	var newPos byte = 100
	switch dir {
	case UP:
		if pos/3 > 0 {
			newPos = pos - 3
			newStep = UP
		}
	case DOWN:
		if pos/3 < 2 {
			newPos = pos + 3
			newStep = DOWN
		}
	case LEFT:
		if pos%3 > 0 {
			newPos = pos - 1
			newStep = LEFT
		}
	case RIGHT:
		if pos%3 < 2 {
			newPos = pos + 1
			newStep = RIGHT
		}
	}
	//fmt.Printf("dir = %d, pos = %d, pos / 3 = %d, pos x 3 = %d, newPos = %d\n",
	//dir, pos, pos/3, pos%3, newPos)
	if newPos != 100 {
		newGrids := exchange(_grids, pos, newPos)
		newSteps := make([]byte, len(step))
		copy(newSteps, step)
		return initState(newGrids, newPos, append(newSteps, newStep))
	} else {
		return nil
	}
}

func contains(s []uint64, e uint64) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func solveByHash(hash uint64, start byte, ansQueryChan chan AnsOp, stepChan chan Result, id string) {
	var grids [9]byte = dehashGrid(hash)
	//fmt.Printf("xxx: %v\n", grids)
	solve(grids, start, ansQueryChan, stepChan, id)
}

func solve(grids [9]byte, start byte, ansQueryChan chan AnsOp, stepChan chan Result, id string) {
	stateList := make([]State, 0) // 记录待遍历的state
	originState := initState(grids, start, []byte{})
	stateList = append(stateList, originState)

	visited := make([]uint64, 0) // 记录访问过的九宫格
	visited = append(visited, originState.hash)

	answer := make([]byte, 0) // 记录找出的最佳答案
	for {
		if len(stateList) == 0 {
			//fmt.Println("end of stateList")
			break
		}
		state := stateList[0]
		stateList = stateList[1:]
		//fmt.Printf("state: %v\n", state)
		//fmt.Printf("%v\n", stateList)
		stepChan := make(chan []byte)
		ansQueryChan <- AnsOp{QUERY, state.stateHash, stepChan, nil}
		baseStep := <-stepChan
		if baseStep != nil {
			if len(answer) == 0 ||
				(len(answer) > len(state.step)+len(baseStep)) {
				answer = append(state.step, baseStep...)
				//fmt.Printf("found answer: %v\n", answer)
			}
		} else if notDone(state.grids) {
			//fmt.Println("not done")
			for _, direction := range DirArr {
				//fmt.Printf("\tdirection: %v\n", direction)
				ifNewState := goNextState(state.grids, direction, state.xPos, state.step)
				if ifNewState != nil {
					newState := ifNewState.(State)
					//fmt.Printf("\t\tnew state: %v\n", newState)
					if len(answer) > 0 && len(state.step) >= len(answer) {
						continue
					}
					if !contains(visited, newState.hash) {
						//fmt.Println("\t\t not contain in visited")
						visited = append(visited, newState.hash)
						stateList = append(stateList, newState)
						//fmt.Printf("\t\t%v\n", stateList)
					}
				}
			}
		} else {
			if len(answer) == 0 ||
				len(answer) > len(state.step) {
				answer = state.step
				//fmt.Printf("done, answer: %v\n", answer)
				if len(answer) == 1 {
					break
				}
			}
		}
	}
	ansQueryChan <- AnsOp{SAVE, originState.stateHash, nil, answer}
	stepChan <- Result{id, answer}
}

func canGo(dir byte, start byte) byte {
	if dir == UP && (start/3 > 0) {
		return start - 3
	} else if dir == DOWN && (start/3 < 2) {
		return start + 3
	} else if dir == LEFT && (start%3 > 0) {
		return start - 1
	} else if dir == RIGHT && (start%3 < 2) {
		return start + 1
	}
	return 100
}

func generate() {
	var hashList []uint64
	var stateList []State
	hashList = make([]uint64, 0)
	stateList = make([]State, 0)

	defaultGrids := [9]byte{0, 1, 2, 3, 4, 5, 6, 7, 8}

	var i byte
	for i = 0; i < 9; i++ {
		newState := initState(defaultGrids, i, []byte{})
		stateList = append(stateList, newState)
		hashList = append(hashList, newState.stateHash)
	}
	sqlFile, err := os.Create("data.sql")
	if err != nil {
		fmt.Println("不能打开文件以输出")
		fmt.Println(sqlFile, err)
		return
	}
	sqlFile.WriteString("insert into puzzles (hash, blank) values \n")
	var state State
	for {
		if len(stateList) == 0 {
			break
		}
		state = stateList[0]
		stateList = stateList[1:]
		for _, direction := range DirArr {
			newPos := canGo(direction, state.xPos)
			if newPos == 100 {
				continue
			}
			var grids [9]byte
			grids[newPos] = state.grids[state.xPos]
			grids[state.xPos] = state.grids[newPos]
			var i byte
			for i = 0; i < 9; i++ {
				if i != newPos && i != state.xPos {
					grids[i] = state.grids[i]
				}
			}
			newState := initState(grids, newPos, []byte{})
			if !contains(hashList, newState.stateHash) {
				hashList = append(hashList, newState.stateHash)
				sqlFile.WriteString(fmt.Sprintf("(%d, %d),\n", newState.hash, newPos))
				stateList = append(stateList, newState)
			}
		}
	}
	sqlFile.Close()
}

func solveAll() {
	dataFile, err := os.Open("puzzles.csv")
	if err != nil {
		fmt.Println(dataFile, err)
		return
	}
	buffIn := bufio.NewReader(dataFile)

	sqlFile, err := os.Create("sqlG")
	if err != nil {
		fmt.Println(sqlFile, err)
		return
	}

	stepChan := make(chan Result)
	calcSize := 0
	go func() {
		for {
			result := <-stepChan
			//if result == nil {
			//return
			//}
			calcSize++
			strStep := ""
			for i, step := range result.step {
				if i == 0 {
					strStep = fmt.Sprintf("%d", step)
				} else {
					strStep = fmt.Sprintf("%s, %d", strStep, step)
				}
			}
			sqlFile.WriteString(fmt.Sprintf("update puzzles set step=%d,solves='%s' where id=%s;\n", len(result.step), strStep, result.id))
		}
	}()

	var ansCache map[uint64][]byte // 以stateHash为key
	ansCache = make(map[uint64][]byte)

	ansQueryChan := make(chan AnsOp)
	go func() {
		for {
			ansQuery := <-ansQueryChan
			//if ansQuery == nil {
			//return
			//}
			if ansQuery.ops == QUERY {
				baseStep, found := ansCache[ansQuery.hash]
				if found {
					ansQuery.stepChan <- baseStep
				}
				close(ansQuery.stepChan)
			} else if ansQuery.ops == SAVE {
				ansCache[ansQuery.hash] = ansQuery.steps
			}
		}
	}()
	recordSize := 0
	for {
		line, err := buffIn.ReadString('\n') //以'\n'为结束符读入一行
		if err != nil || io.EOF == err {
			break
		}
		recordSize++
		puzzles := strings.Split(line, ",")                // puzzleId, puzzleHash, step, blank, solves
		hash, err := strconv.ParseUint(puzzles[1], 10, 64) // 把字符串转成10进制数，64位
		if err != nil {
			fmt.Printf("读取hash失败 %v\n", puzzles)
		}
		grids := dehashGrid(hash)
		start, err := strconv.ParseInt(puzzles[3][:1], 10, 8)
		if err != nil {
			fmt.Println(err.Error())
			fmt.Printf("读取start失败 %v\n", puzzles)
		}
		go solve(grids, byte(start), ansQueryChan, stepChan, puzzles[0])
		time.Sleep(20 * time.Millisecond) // 等待20毫秒
	}
	for calcSize != recordSize {
		time.Sleep(5 * time.Second) // 等待五秒
	}
	sqlFile.Close()
	dataFile.Close()
}

func main() {
	solveAll()
}
